package SortStudy;

import java.util.Stack;

public class Sort {

    /*
    *  插入排序
    *时间复杂度:
    *   最好情况:数据有序情况下:O(N)
    *   最坏情况:数据逆序的:O(N²)
    *空间复杂度:O(1)
    *稳定性: **稳定的**
    *   一个本身就不稳定的排序,是不可能成为稳定的排序的
    *   但一个本身就稳定的排序,是可以实现稳定的排序的
    *特点: 数据越有序 , 直接插入排序越快
     */
    public static void insertSort(int[] array){
        int n = array.length;
        //插排,默认第一个有序,所以从第二个元素1下标开始遍历
        for(int i = 1; i < n ; i++){
            int j = i - 1;
            int tmp = array[i];
            for( ; j >= 0 ; j--){
                if(tmp < array[j]){
                    array[j+1] = array[j];//tmp < j 时 - ①
                }else{
                    //array[j+1] = tmp;//tmp > j 时 - ②
                    break;
                }
            }
            //当j将前面第一个元素都遍历完了,j就会走到-1说明tmp比后面所有元素都小,所以直接将其插入到0位置即可:
            //即array[i+1] = tmp
            array[j+1] = tmp; // ③ j遍历完i前面所有元素 tmp 都没找到小于j的 , 此时它和情况②的代码一样,我们可以将上面注释掉,防止多赋值一次
            //因为break以后会运行这个③的代码
        }

    }


    //希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;//一开始可以以数组的长度进行分组
        while(gap > 1){
            //当分组还是比1大时,继续往下分组,直到1
            gap = gap / 3 + 1;
            shell(array , gap);
        }

        //处理gap为1时的情况
        shell(array , 1);
    }

    private static void shell(int[] array , int gap){//希尔排序的插排方法
        int n = array.length;
        //插排,默认第一个有序,所以从第二个元素1下标开始遍历
        for(int i = gap; i < n ; i++){
            int j = i - gap;
            int tmp = array[i];
            for( ; j >= 0 ; j-=gap){
                if(tmp < array[j]){
                    array[j+gap] = array[j];//tmp < j 时 - ①
                }else{
                    //array[j+1] = tmp;//tmp > j 时 - ②
                    break;
                }
            }
            //当j将前面第一个元素都遍历完了,j就会走到-1说明tmp比后面所有元素都小,所以直接将其插入到0位置即可:
            //即array[i+1] = tmp
            array[j+gap] = tmp; // ③ j遍历完i前面所有元素 tmp 都没找到小于j的 , 此时它和情况②的代码一样,我们可以将上面注释掉,防止多赋值一次
            //因为break以后会运行这个③的代码
        }
    }


    /*
    *选择排序:
    *   时间复杂度:O(N²)
    *   空间复杂度:O(1)
    *   稳定性: 不稳定
     */
    public static void selectSort(int[] arr){
        int n = arr.length;
        for(int i = 0 ; i < n ; i++){
            int minIndex = i;
            for(int j = i+1 ; j < n ; j++){
                if(arr[j] < arr[minIndex]){
                    //先把j的值存在临时变量的下标里
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    public static void swap(int[] array , int a , int b){
        int tm = array[a];
        array[a] = array[b];
        array[b] = tm;
    }

    //选择排序排法②:
    public static void selectSort2(int[] arr){
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1; i <=  right ; i++){
                if(arr[i] < arr[minIndex]){
                    minIndex = i;
                }else if(arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }
            }

            swap(arr,minIndex,left);
            //第一次交换 最大值可能是left,然后被换到了minIndex的位置
            if(maxIndex == left){
                maxIndex = minIndex;
            }

            swap(arr,maxIndex,right);
            left++;
            right--;
        }
    }


    /*
    * 堆排序
    * 时间复杂度: O(N*log(n))
    * 空间复杂度: O(1)
    * 稳定性: 不稳定排序
     */
    //堆排序
    public static void heapSort(int[] arr){
        //1.创建大根堆
        createHeap(arr);
        //2.先创建获取最后一个叶子结点下标的变量end
        int end = arr.length - 1;
        while(end > 0){
            // 3.将堆顶元素和最后的叶子结点的值交换
            swap(arr,0,end);
            // 4.交换完成,继续调整为大根堆
                //调整时:从根节点往下调一直到没有被交换的叶子结点end-1这个的位置
            shiftDown(arr,0,end - 1);//因为end已经换好了,换好了就不用动
            // 5.end继续减减
            end--;
        }
    }

    //创建大根堆的方法
    public static  void createHeap(int[] arr){
        //创建大根堆从最后一颗子树开始创建
        int len = arr.length;
        int child = arr.length - 1;
        for(int parent = (child - 1)/2 ; parent >= 0 ; parent--){
            shiftDown(arr,parent,len);
        }
    }

    //每一颗子树向下调整找大根
    public static void shiftDown(int[] arr , int parent , int len){
        int child = (2 * parent) +1;
        while(child < len){
            //当未调整完时,孩子节点值小于节点总数,因为每一颗树都要调整,每调整完一次孩子节点就++;
            //下面是对每一颗子树左右孩子进行的相关操作
            //判断有右子树 并且 右树大于左树
            if (child +1 < len && arr[child] < arr[child + 1]){
                child = child +1;//获取右孩子的下标(因为它是最大值,需要记录下来与父母节点交换)
            }
            //如果只有左孩子 或 是已经走完上面语句获取右孩子下标
            //此时我们需要将他们和父母节点的值作比较
            //如果孩子节点的值大于父母节点就需要交换他两
            if(arr[child] > arr[parent]){
                heapSwap(arr , child , parent);
                //交换完,让p继续走到孩子节点作为父母节节点根据关系式去找它的孩子节点
                parent = child;
                child = 2*parent + 1;
            }else{
                //如果父母节点大于孩子节点就不交换;
                break;
            }
        }
    }

    //创建堆里面父母和孩子交换的方法
    public static void heapSwap(int[] arr , int parent , int child){
        //创建临时变量存储其中一个的值
        int tmp = arr[parent];
        arr[parent] = arr[child];
        arr[child] = tmp;
    }

    /*
    *冒泡排序
    * 在不带优化条件下
    * 最好和最坏的情况 时间复杂度都是: O(N²)
    * 空间复杂度: O(1)
    * 稳定性:稳定
     */
    public static void bubbleSort(int[] arr){
        //循环趟数 n个元素 , 循环 n - 1 趟
        int n = arr.length;
        for(int i = 0 ; i < n - 1 ; i++){
            //优化排序:设置一个布尔变量,先给他赋值为false
            //表示它一开始就是有序的,无需进行排序
            boolean order = false;
            //循环比较次数 , 每一趟的比较次数和次数的关系为: j < len - i - 1
            for(int j = 0 ; j < n - 1 - i ; j++){
                if(arr[j] > arr[j+1]){
                    swap(arr , j , j+1);
                    //只要发生交换,说明无序,order为true
                    order = true;
                }
            }
            // 若未进行交换,说明有序
            if(order == false){
                return;
            }
        }
    }


    /*
    * 快速排序
    * 时间复杂度:
    *   最好情况下:O(N*log(N)
    *   最坏情况:O(N²)  有序/逆序
    * 空间复杂度:
    *   最好:O(logN)
    *   最坏:O(N)
    * 稳定性:
    *   不稳定排序
     */
    public static void quickSort(int[] arr){
        quick(arr , 0 , arr.length - 1);
    }

    private static void quick(int[] arr , int start , int end){
        //递归结束的条件
        //对于左树:
            //如果它基准值pivot左边没有元素,递归结束条件是:start>end(是-1)
            //如果它基准值pivot左边有元素,递归结束条件是:start = end
        if(start >= end){
            return;
        }

        //递归到最小的子区间时考虑插排
        if(end - start + 1 <= 10){
            NewinsertSort(arr,start,end);
            return;
        }

        //优化方式: ①.三数取中
        int index = middleNum(arr,start,end);//获取中间大的值的下标
        swap(arr,index,start);//将中间大的值和最左边的值交换,下面传入的值就是中间大的值了
        //找到分治的分界点pivot
        int pivot = partition(arr,start,end);//
        //递归左边
        quick(arr , start , pivot - 1 );
        //递归右边
        quick(arr , pivot + 1 , end);
    }

    public static void NewinsertSort(int[] array , int start , int end){
        int n = array.length;
        //插排,默认第一个有序,所以从第二个元素1下标开始遍历
        for(int i = start + 1; i <= end ; i++){
            int j = i - 1;
            int tmp = array[i];
            for( ; j >= start ; j--){
                if(tmp < array[j]){
                    array[j+1] = array[j];//tmp < j 时 - ①
                }else{
                    //array[j+1] = tmp;//tmp > j 时 - ②
                    break;
                }
            }
            //当j将前面第一个元素都遍历完了,j就会走到-1说明tmp比后面所有元素都小,所以直接将其插入到0位置即可:
            //即array[i+1] = tmp
            array[j+1] = tmp; // ③ j遍历完i前面所有元素 tmp 都没找到小于j的 , 此时它和情况②的代码一样,我们可以将上面注释掉,防止多赋值一次
            //因为break以后会运行这个③的代码
        }

    }

    private static int middleNum(int[] arr , int left , int right){
        int mid = left + (right - left) >> 1;//获取中间值的下标 >>1表示除2

        //比较三获取三数中中间大的那个数
        if(arr[left] > arr[right]){
            if (arr[mid] > arr[left]){
                return left;
            }else if(arr[right] > arr[mid]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(arr[mid] > arr[right]){
                return right;
            }else if(arr[left] > arr[mid]){
                return left;
            }else{
                return mid;
            }
        }
    }

    //找到分界点的方法
    /*
    *方法一:Hoare法
     */
    private static int partition1(int[] arr , int left , int right){
        //定义变量存基准值
        int tmp = arr[left];
        //存放以基准值划分数组时的最左边left一开始的下标
        int i = left;
        while(left < right){
            //先从右边开始往前找比基准值小的数
            //但是,right -- 的时候,下面循环不够严谨,当数组的基准值左边没有元素时(s正好在pivot时)
            //right-- , 会发生越界,因此要给下面循环加上一个限制条件:right > left
            while(left < right && arr[right] >= tmp){
                right--;
            }

            //同上,左边找比基准值大的
            while(left < right && arr[left] <= tmp){
                left++;
            }

            //将上面符合条件的left和right交换
            swap(arr,left,right);

        }

        //当left = right 时
        //我们先定义一个变量i存放以基准值划分的数组时的最左边left一开始的下标
        //然后当left和right相遇时,left指向的就是基准值嘛
        //然后让基准值和最左边的值交换
        swap(arr,i,left);
        //最后返回相遇的位置left -> 就是最终存放基准值的下标
        return left;
    }

    /*
    *方法2:挖坑法
    *
     */
    public static int partition(int[] arr , int left , int right){
        int tmp = arr[left];//基准值
        while(left < right){

            //以上面的基准值为界进行递归
            //右子树递归
            while(left < right && arr[right] >= tmp){//必需取等号,否则会发生死循环
                right--;
            }
            // 遇到比基准值小的,将右边元素往左边的空位放
            arr[left] = arr[right];

            //左子树递归
            while(left < right && arr[left] <= tmp){
                left++;
            }
            // 遇到比基准值大的,将左元素往右边的坑位放
            arr[right] = arr[left];
        }
        //将基准值放到两个指针相遇的位置
            arr[left] = tmp;
        //返回基准值的位置
        return left;
    }


    /*
    *   非递归实现快排
     */

    public static void quickSortNor(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int pivot = partition(arr,left,right);//基准值

        //1.创建一个栈
        Stack<Integer> mystack = new Stack<>();
        //先分别判断基准值左右子树元素是否>=2,是就将左右子树分别入栈
        if(pivot - 1 > left){
            mystack.push(left);
            mystack.push(pivot - 1);
        }
        if(pivot + 1 < right){
            mystack.push(pivot + 1);
            mystack.push(right);
        }
            while(!mystack.isEmpty()){
                right = mystack.pop();
                left = mystack.pop();
                pivot = partition(arr , left , right);
                if(pivot - 1 > left){
                    mystack.push(left);
                    mystack.push(pivot - 1);
                }
                if(pivot + 1 < right){
                    mystack.push(pivot + 1);
                    mystack.push(right);
                }

            }
        }

    /*
    *归并排序
    *
    *
     */
    public static void mergeSort(int[] arr){
        mergeFunc(arr , 0 , arr.length - 1);
    }

    public static void mergeFunc(int[] arr , int left , int right){
        if(left >= right){
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeFunc(arr,left,mid);//左边分解
        mergeFunc(arr,mid+1,right);//右边分解
        //左边分解完,右边分解完,开始合并
        merge(arr,left,mid,right);

    }

    //合并方法
    private static void merge(int[] arr, int left , int mid , int right){

        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;

        //创建一个新的空数组存放排序的元素
        int[] tmpArr = new int[right - left + 1];
        //将数组下标记为k
        int k = 0;

        //1.保证两个表都有数据
        while(s1 <= e1 && s2 <= e2){
            //每次都是比较s1和s2
            if(arr[s1] <= arr[s2]){
                tmpArr[k++] = arr[s1++];
            }else{
                tmpArr[k++] = arr[s2++];
            }
        }

        //2.比较完,肯定有一个数组还有数据,一个没有,将还有数据的那个数组拷贝回去
        while(s1 <= e1){
            tmpArr[k++] = arr[s1++];
        }
        while(s2 <= e2){
            tmpArr[k++] = arr[s2++];
        }

        //3.将新数组的数据拷贝到源数组
        for(int i = 0 ; i < k ; i++){
            //因为左右两个数组的起始拷贝位置不都是从0开始的,所以为了正确拷贝
            //我们在这个基础上加上它们自己的left下标
            arr[i+left] = tmpArr[i];
        }

    }

    /*
    *非递归实现归并排序
    * 时间复杂度:O(N*logN)
    * 空间复杂度:O(N)
    * 稳定性:稳定
     */
    public static void mergeSortNor(int[] arr){
        //1.先一个一个为一组
        int gap = 1;
        //2.最外层循环,控制组数
        while(gap < arr.length){
            //然后2个2个为一组,4个4个位一组进行归并
            for(int i = 0 ; i < arr.length ; i = i+2*gap){
                int left = i;
                int mid = left + gap - 1;
                //判断中间是否会越界
                if(mid >= arr.length){
                    mid = arr.length - 1;
                }
                //判断右边是否会越界
                int right = mid + gap;
                if(right >= arr.length){
                    right = arr.length - 1;
                }
                merge(arr,left,mid,right);
            }
            //最后8个为一组,说明已排好序
            gap *= 2;
        }
    }


    /*
    计数排序
    时间复杂度: O(MAX(N,范围))
    空间复杂度:O(范围)
    稳定性:稳定
     */
    public static void counterSort(int[] arr){
        //1.求最值
            //先假设最值就是数组的第一个值
        int min = arr[0];
        int max = arr[0];
            //通过循环遍历无序数组arr每一个元素,通过比较获取最大值和最小值
        for(int i = 0 ; i < arr.length ; i++){
            if(arr[i] < min){
                min = arr[i];
            }
            if(arr[i] > max){
                max = arr[i];
            }
        }

        //2.初始化计数数组 - > 长度为排序区间
        int[] count = new int[max - min + 1];
        //初始化计数数组
        for(int j = 0 ;  j < arr.length ; j++){
            int index = arr[j] ;//像90-99这样的区间可以将它们区间内的数-90得到一个下标为0-9的数组
            count[index - min]++;
        }

        //3.遍历计数数组,将排好序的数组按照从小到大依次打印出来
        int k = 0;//表示arr数组下标
        for(int i  = 0 ; i < count.length ; i++){
            while(count[i] != 0){
                arr[k] = i + min;
                k++;
                count[i]--;
            }
        }

    }

}



